package sortAlgorithm;

/**
 * 基数排序
 * 
 * @author YNS
 *
 */
public class RadixSort {
	public static int[] sort(int[] source) {
		int maxLength = 0;
		for (int i = 0; i < source.length; i++) {
			if (maxLength < source[i])
				maxLength = source[i];
		}
		// 根据最大数求最大长度
		maxLength = String.valueOf(maxLength).length();

		// 用于暂存数据的数组
		int[][] temp = new int[10][source.length];
		// 用于记录temp数组中每个桶内存的数据的数量
		int[] counts = new int[10];
		// 用于记录每个数的i位数
		int num = 0;
		// 用于取的元素需要放的位置
		int index = 0;
		// 根据最大长度决定排序的次数
		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			for (int j = 0; j < source.length; j++) {
				num = source[j] / n % 10;
				temp[num][counts[num]] = source[j];
				counts[num]++;
			}

			// 从temp中取元素重新放到arr数组中
			for (int j = 0; j < counts.length; j++) {
				for (int j2 = 0; j2 < counts[j]; j2++) {
					source[index] = temp[j][j2];
					index++;
				}
				counts[j] = 0;
			}
			index = 0;
		}
//	        System.out.println(Arrays.toString(source));

		return source;
	}
}
